package com.LeeCode;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 统计趣味子数组的数目
 */

public class Code2845 {
    public static void main(String[] args) {

    }

    public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
        if (modulo <= k) return 0; // 边界条件

        Map<Integer, Integer> modCount = new HashMap<>();
        modCount.put(0, 1); // 初始化
        long ans = 0;
        int prefixMod = 0;

        for (int num : nums) {
            if (num % modulo == k) {
                prefixMod = (prefixMod + 1) % modulo;
            }
            // 我们要找 (prefixMod - x) % modulo == k => x ≡ (prefixMod - k) % modulo
            int target = (prefixMod - k + modulo) % modulo;
            ans += modCount.getOrDefault(target, 0);
            modCount.merge(prefixMod, 1, Integer::sum);
        }
        return ans;
    }
}
